Given an array of $n$ elements from a total order, we propose encodings thatsupport various range queries (range minimum, range maximum and theirvariants), and previous and next smaller/larger value queries. When query timeis not of concern, we obtain a $4.088n + o(n)$-bit encoding that supports allthese queries. For the case when we need to support all these queries inconstant time, we give an encoding that takes $4.585n + o(n)$ bits, where $n$is the length of input array. This improves the $5.08n+o(n)$-bit encodingobtained by encoding the colored $2d$-Min and Max heaps proposed byFischer~[TCS, 2011]. We first extend the original DFUDS [Algorithmica, 2005]encoding of the colored 2d-Min (Max) heap that supports the queries in constanttime. Then, we combine the extended DFUDS of $2d$-Min heap and $2d$-Max heapusing the Min-Max encoding of Gawrychowski and Nicholson [ICALP, 2015] withsome modifications. We also obtain encodings that take lesser space and supporta subset of these queries.
展开▼
